1. Field of the Invention
This invention relates generally to trellis coded modulation techniques for use in digital communication systems. More particularly, the invention relates to methods and apparatus for the encoding and decoding of two-dimensional and higher-dimensional trellis-encoded signal constellations using an efficient and practical multilevel form of trellis coded modulation.
2. Description of the Related Art
A family of WiMAX trellis codes is discussed in IEEE Std. 802.16a 2004 “WiMAX standard”, which is incorporated herein by reference; see especially sections 8.2-8.4. Many relevant details of the WiMAX trellis codes are described herein. For example, see FIGS. 1a-1e herein which reproduce FIGS. 161, 163, 165, 167, 174, 175 and 171 from the IEEE 802.16a-2004 standard. In the disclosure herein, the term “trellis code” should be understood to refer generally to a single-level or multilevel trellis coded modulation scheme, i.e. a “trellis code” as used herein includes convolutionally encoded bits, optional uncoded bits, and a bit mapper that maps these bits to a trellis coded signal constellation.
FIG. 1a also shows a 64-state, rate-½ convolutional coder 161 that gives rise to a code with a free Hamming distance of dfree=10. This large free Hamming distance is desirable because it can be used to multiplicatively extend the minimum squared Euclidian distance (MSED) between adjacent signal constellation points. For example, if the uncoded MSED between neighboring constellation points in a small and compact signal constellation with no uncoded bits is D2, the trellis encoder 161 can increase this to a coded MSED of dfree×<D2=10×D2. In larger constellations that also include uncoded bits, the actual MSED improvement is typically much less. A good source of reference to understand many theoretical aspects of the present invention is “Error control coding, 2nd Ed.,” by Shu Lin and Daniel J. Costello, Jr., Prentice Hall, 2004, (“the Lin and Costello reference”). Table 12.1 (pages 539-540) of the Lin and Costello reference tells how many states are needed for a convolutional code to achieve a given Hamming distance at a given coding rate, e.g., rate-½, rate-⅔, or rate-¾. These tables are very useful when designing trellis codes as discussed below.
FIG. 1a shows a prior art rate-¾ trellis encoder 163 constructed by mapping two coded bits produced by the rate-½ encoder 161 onto an I-component (in-phase) and a Q-component (quadrature-phase) to produce a trellis coded 16-QAM constellation 174a as shown in FIG. 1c. To better understand the operation of encoder 163 we start by defining what we call a 4-QAM (or, QPSK) “coded constellation building block,” 20 which is illustrated in FIG. 2. This constellation building block can be thought of as a direct I/Q mapping of the X and Y outputs of the rate-½ convolutional encoder 161. That is, a 2D building block encoder 215 can be implemented using a rate-½ coder such as the coder 161 to generate the 2D 4-QAM building-block constellation 20. The X and Y outputs of the rate-½ convolutional encoder 161 respectively correspond to coded bits c1 and c0. The encoder 163 maps the encoder 161's coded bits along with two uncoded bits onto a 16-QAM constellation 174a as shown in FIG. 1c. The present invention is based in part of the observation that this 16-QAM constellation can be viewed as a tiling of four copies of the 4-QAM building block of FIG. 2 into the four quadrants of the I/Q plane, centered at the four points, (±2, ±2), which we call tiling points. More generally, in trellis coded modulated systems, a constellation building block typically corresponds to the lower order bits which are trellis coded, i.e., with no uncoded bits. As discussed in further detail below, the uncoded bits then have the effect of replicating this building block and tiling onto larger trellis coded signal constellations.
The minimum squared Euclidian distance (MSED) between uncoded constellation points within the 4-QAM coded building block 20 can be readily seen to be D2=4. Any change of a single coded bit in FIG. 2 contributes to the Euclidian distance by an amount 4. Therefore, if the convolutional encoder 161 (dfree=10) is used to encode the input bits to the building block 20, that the MSED between coded trellis sequences on the 4-QAM building block 20 increases to D2=4×10=40. The encoder 163 maps the coded bits of the building block 20 along with two uncoded bits. As mentioned above, the addition of the uncoded bits has the effect of placing (or “tiling”) one of the 4-QAM coded building blocks 20 in each quadrant of the constellation 174a, centered at the tiling points (±2, ±2). While the minimum distance between trellis sequences inside each of these 4-QAM building blocks 20 is D2=40, the MSED between trellis sequences encoded onto the 16-QAM constellation 174a using encoder 163 is only D2=16. It would be desirable to have an efficient and low cost way of improving upon this MSED, for example, to bring the MSED of the 16-QAM constellation 174a up to D2=40 or higher.
FIG. 3 shows a block diagram of a prior art rate-¾ punctured encoder 30 used in the WiMAX standard. The encoder 30 generates a punctures the code 161 to generate the puncture-coded version of 16-QAM constellation 171 of FIG. 1e. That is, it uses a different rate-¾ encoding rule than the one used by encoder 163 and also maps this on to a Gray code enumerated signal constellation 171. FIG. 3 is not provided in the 802.16a-2004 standard but can be derived by studying FIGS. 161 and 165 and using Table 174 of the 802.16a-2004 standard (Table 174 not reproduced herein). Table 174 of the 802.16a-2004 standard identifies a specific puncturing pattern used by the punctured rate-¾ encoder 30 portion of an encoder 165 shown in FIG. 165 of FIG. 1b. 
Because the encoder 30 does not map any uncoded bits, FIG. 3 can be viewed as directly generating a 16-QAM constellation building block which uses the Gray-coded 16-QAM constellation 171. The combination of the punctured coding 30 and the Gray code constellation enumeration allow the coded constellation 171 to achieve an MSED of D2=20 instead of the 16-QAM constellation 173's MSED of D2=16. The encoder 165 additionally takes in two uncoded bits which cause the bit mapper portion of the encoder 165 to tile four copies of the 16-QAM building block 171, one in each quadrant, to form the rate-⅚ trellis coded 64-QAM constellation 174b. This time the building blocks are bigger (16-QAM vs. 4-QAM), so they are centered at tiling points (±4, ±4). Because the tile centers are at (±4, ±4), the distance between 16-QAM tile centers is D=8 or D2=64. This larger distance between tile centers does not affect the overall MSED, so that the 16-QAM building block 171 dominates and the MSED of the 64-QAM constellation 165 is D2=20.
Also shown in FIG. 1b is a coder 167. The coder 167 also uses the same punctured rate-¾ encoder 30, but maps this along with four uncoded bits to provide an overall rate-⅞ trellis coded 256-QAM constellation 175 of FIG. 1d. The encoder 167 can be thought of as tiling sixteen copies of the 16-QAM building block 171 by mapping their centers to points (±4, ±4) and (±4, ±12), (±12, ±4) and (±12, ±12) of the constellation 175. Note that the distance between tile centers in both the 64-QAM and the 256-QAM constellations is D=8, or D2=64. The 16-QAM building blocks 171 (or, “tiles”) generated by the encoder 30 have an intra-block MSED of D2=20 and an inter-block (or “inter-tile”) MSED between tile centers of D2=64. The MSED of the coded 256-QAM constellation 175 thus also achieves an overall MSED of D2=20. This distance is lower because the encoder 30 is a rate-¾ coder and its effective free Hamming distance is five. However, since D2=20<64, the MSED of this larger 16-QAM building block 171 is not diminished once it is tiled. That it, the 16-QAM building block 171's MSED is preserved after tiling in both the constellations 174b and 175 because the larger tile 171's centers are spaced far enough apart, i.e., D2=64. It would be desirable to have an efficient and low cost way of improving upon this MSED by being able to efficiently tile smaller building blocks with higher MSED without loosing the benefit due to closer-space tiling points.
Another example of a trellis coded modulation scheme is the LSB (least significant bit) coding technique used in the ITU-J.83 digital television transmission standard. J.83 transmission is also used in the down link of DOCSIS cable modems. As illustrated in FIG. 4, in LSB-coded signal constellations, each of the I and Q dimensions of the QAM constellation are indexed independently in such a way that the LSB of each dimension alternates along the I and Q axes. In FIG. 4, note that the right-most bit of each signal point alternates between successive signal points along the Q-dimension and the next-right-most bit alternates between successive signal points along the I-dimension. LSB codes create an overall checker-board pattern where the different subsets correspond to the red and black squares of a checkerboard. The LSB codes treat the I and Q axes of the QAM constellation like separate real-valued PAM constellations. Constellation points in each of these component PAM constellations alternate between LSB=0 and LSB=1 subsets. For example in FIG. 4 going along the Q-direction, constellation points in any column can be grouped into an LSB=0 set if the LSB of the constellation point's corresponding right-most bit is 0, or into an LSB=1 set if the LSB of the constellation point's corresponding right-most bit is 1. Similarly, going along the I-direction, any row of constellation points can be grouped into the LSB=0 set if the next-rightmost LSB of the constellation point's corresponding bit sequence is 0, or into the LSB=1 set if the next-rightmost LSB of the constellation point's corresponding bit sequence is 1. When bits have been generally mapped in this way, we say that the LSB-coding bit mapping rule 40 has been employed. The MSED between the LSB=0 and LSB=1 subsets in each dimension can be increased applying the next-rightmost and right-most LSBs to respective I and Q convolutional coders. As discussed below, in this disclosure we use LSB coding for tiling operations, so we have labeled the axes of FIG. 4 to spread points twice as far apart as the J.83 standard. Using this labeling, the distance between adjacent constellation points is D=4 or D2=16 (this relabeling will not change performance or normalized minimum distance but is useful herein). If the free Hamming distance of the convolutional code used in the LSB encoder is dfree, then MSED between the LSB=0 and LSB=1 subsets is increased by a factor dfree. In J.83, a pair of 16-state LSB encoders with a Hamming distances of three is used. This increases the MSED between the adjacent sequences corresponding to the same LSB subset to D2=3×16=48. If an LSB coder with Hamming distance dfree=4 is chosen, then the distance between adjacent points in the same LSB subset increases to D2=4×16=64. If a convolutional code with dfree>4 is selected for use with the LSB code, no further MSED will be obtained because bit errors in the next-least-significant (uncoded) bit correspond to a distance of D2=64. Therefore if a tiling code with D2>64 is desired, more than just the LSBs would need to be protected.
FIG. 5 shows a J.83 constellation encoder 12 that can generate the LSB-coded QAM constellation of FIG. 4 when Nuc=2 uncoded bits are used. When the J.83 trellis encoder 61a of FIG. 6 is used in the constellation encoder of FIG. 5, the MSED between adjacent constellation points is increased by a factor of three over an uncoded QAM constellation. As discussed in the 1998 Gather and Ali article (see accompanying IDS), other trellis encoders such as the 32-state encoder 61b or the 64-state encoder 61c can also be used with the constellation encoder of FIG. 5. The encoders 61b and 61c have a free Hamming distance of dfree=4 and thus multiply the MSED between adjacent sequences by a factor of four over an uncoded QAM constellation, giving D2=4×16=64. Going to higher-state codes with dfree>4 cannot increase this distance further in the prior art LSB approach. This is because the squared distance between points in the LSB=0 and LSB=1 subsets is capped by D2=64. While LSB codes are highly efficient and simple to implement, it would be desirable to have an improved trellis coded modulation system that can provide further gains over prior art LSB encoded systems such as the trellis codes used in the J.83 standard. It would also be desirable to use the above LSB codes to improve tiling performance of larger constellations created by tiling building blocks onto an integer lattice.
As used herein, “integer lattice” is generally ZN or a subset of ZN, where ZN denotes the integer points of an N-dimensional vector space. In some cases the integer points may include complex integers (i.e., a+jb where a and b are integers). The vector space CN of complex numbers is generally taken to be an N-dimensional “signal space.” Received signals in a receiver are processed and most often converted to points in the signal space. A decoder portion of the receiver attempts to map sequences of the received signal points in CN back onto complex integers of the integer lattice, e.g. ZN. The integer lattice is also a subset of CN. An integer lattice generally extends to infinity and a given trellis encoder maps bits to a signal constellation which is finite and is thus a subset of the integer lattice.
Yet another example of a trellis coded modulation scheme is the Wei family of multidimensional trellis codes. Such codes are described in detail in U.S. Pat. No. 4,713,817, which is incorporated herein by reference. FIG. 7a shows a constituent 2D signal constellation 70 used in the 4D Wei codes. FIG. 7b shows Wei's 4D coder 75 used to generate his 4D 16-state code. FIG. 8a shows a constituent 2D signal constellation 80 used in the 8D Wei codes. FIG. 8b shows Wei's 8D coder 85 used to generate his 8D 64-state code. While these codes are highly advantageous, their coding gain is limited by an inherent constellation expansion that comes about as an artifact of code construction. Note that Wei's 4D encoder 75 takes in fourteen bits each 4D mapping frame, i.e., m=7 bits per 2D signaling interval. To send seven bits using an uncoded constellation requires 128 constellation points, normally transmitted using a 128 CR (cross) constellation. Wei's 192-point constituent 2D constellation 70 has sixty-four more points than the uncoded 128 CR (cross) constellation that would be needed to send the same seven bits per interval if no coding were employed. The 128 CR constellation is made up of the 128 points inside the crosses drawn in FIGS. 7a and 8a. Cross constellations come about when an odd number of bits, m, are sent each 2D signaling interval. If an even number of bits is sent each 2D interval, the constellation typically has a square shape. If a fractional number of bits are sent each interval, the constellation takes on some other shape. For example, the signal constellation 70 has 27+27×0.5=128+64=192 points, and can thus carry 7.5 bits per interval, while the constellation 80 has 27+27×0.25=128+32=160 points and can thus carry 7.25 bits per interval.
On page 492 of Wei's IEEE Transactions on Information Theory article, Vol. IT-33, July 1987 (“Wei'87”) (incorporated by reference herein), Wei explains that his 16-state 4D trellis code looses 1.36 dB due to constellation expansion. Col 2 of p. 492 of Wei '87 states: “[4.66 dB] is also the largest possible coding gain that can be achieved with the partitioning of the 4D rectangular constellation of Table I.” Col. 2 of p. 496 states: “Given the partitioning of the 4D or 8D rectangular constellation of section IV-A or -B, it is impossible to increase the coding gain further or reduce the error coefficient of the 16-state or 64-state code of those two subsections.” It would be desirable to recapture the bulk of this coding loss due to constellation expansion with increase in coding/decoding complexity on the order of some small amount like 25%-45%.
Another related area of art in need of improvement relates to multilevel codes. For example, see the articles provided in the accompanying IDS entitled “Multilevel Codes: Theoretical Concepts and Practical Design Rules,” by Wachsmann et al, IEEE Transactions on Information Theory, vol. 45 no. 5, July 1999, and “Coded Modulation by Multilevel-Codes: Overview and State of the art, by J. Huber et al; and “Multilevel Codes: Distance profiles and Channel Capacity,” 1994, by J. Huber. These articles discuss a family of multilevel coders and decoders. The coders described in these articles generally maintain specified coding rates on each of a plurality of bit lines, use long interleavers, have larger delays, are relatively complex to implement, and use a subset partitioning technique that creates subsets of points that are spread out at a lower level partitioning but are clustered at upper levels. It would be advantageous to have a multilevel coding scheme that could be characterized generally as a multilevel code, but that was much simpler to implement. It would be desirable to have a multilevel coding scheme assigns groups of points in lowest level partition to tight clusters around tile points in an upper level coding partition. It would be advantageous to provide efficient multilevel coding structures and methods that whose implementation complexity is on the same order as current trellis coded modulation schemes already used in various telecommunication standards. A simple and efficient family of multilevel coding and decoding schemes would be useful in improving existing trellises coded modulation schemes such as the ones found in various telecommunication standards.